package week3.exer02;

import java.util.Scanner;

/**
 * 题目描述：
 * 在n枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，已知道假币比真币轻。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。要求用分治法称重来实现。
 * 输入要求：
 * 第1行输入一个整数n（2<=n<=100），表示有n个硬币。
 * 第2还开始输入n个整数，表示每个硬币的重量。
 *
 * 输出要求：
 * 输出一个整数(1…n)，表示假币是第几个硬币。
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }
        System.out.println(partition(coins, 0, n - 1) + 1);
    }

    private static int partition(int[] coins, int left, int right) {
        if (left == right) {
            return left;
        }
        int totalCount = right - left + 1;
        int leftSum = 0;
        int rightSum = 0;
        int mid = (left + right) / 2;
        if (totalCount % 2 != 0) {
            for (int i = left; i < mid; i++) {
                leftSum += coins[i];
            }
            for (int i = mid + 1; i <= right; i++) {
                rightSum += coins[i];
            }
            if (leftSum == rightSum) {
                return mid;
            } else if (leftSum < rightSum) {
                return partition(coins, left, mid - 1);
            } else {
                return partition(coins, mid + 1, right);
            }
        } else {
            for (int i = left; i <= mid; i++) {
                leftSum += coins[i];
            }
            for (int i = mid + 1; i <= right; i++) {
                rightSum += coins[i];
            }
            if (leftSum < rightSum) {
                return partition(coins, left, mid);
            } else {
                return partition(coins, mid + 1, right);
            }
        }
    }
}
